home *** CD-ROM | disk | FTP | other *** search
/ POINT Software Programming / PPROG1.ISO / pascal / swag / sorting.swg / 0033_Alpha Sorting.pas < prev    next >
Encoding:
Pascal/Delphi Source File  |  1993-08-27  |  3.6 KB  |  122 lines
  1. {
  2. GREGORY P. SMITH
  3.  
  4. > Well, that's easier said than done !  So far I've accomplished a
  5. > selection sort which takes about 10-15 minutes For 1000 Records, and I'm
  6. > gonna be needin to sort about 5000 For the Programz intended application
  7. > !!! Also the place that I'm writing this For has an 8088 With 640K RAM
  8. > <chuckle> !!! Could you pleez tell me how to do a merge sort <is that
  9. > easier than quicksort
  10.  
  11. Here is an example followed by an exlpanation.
  12. }
  13.  
  14. Type
  15.   ListPtr = ^List;
  16.   List = Record
  17.     next : ListPtr; { next node }
  18.     str  : String;  { data to sort }
  19.   end;
  20.  
  21. { Splits List l into two half lists, h1 & h2 }
  22. Procedure SplitList(l : ListPtr; Var h1, h2 :  ListPtr);
  23. Var
  24.   listone : Boolean;
  25.   tmp : ListPtr;
  26. begin
  27.   h1 := nil;
  28.   h2 := nil;
  29.   listone := True;            { start With first list }
  30.   While l <> nil do
  31.   begin
  32.     tmp := l^.next;           { save next node to split }
  33.     if listone then
  34.     begin                     { insert a node in the first list }
  35.       l^.next := h1;
  36.       h1 := l;                { keep h1 at head }
  37.     end
  38.     else
  39.     begin                     { insert a node in the second list }
  40.       l^.next := h2;
  41.       h2 := l;                { keep h2 at head }
  42.     end;
  43.     l := tmp;                 { move to next node }
  44.     listone := not listone;   { alternate lists to insert into }
  45.   end;
  46. end; { SplitList }
  47.  
  48. {----------------- Merge Sort -------------------}
  49.  
  50. { merges sorted l1 & l2 into one sorted list (alphabetically) }
  51. Function MergeAlphaLists(l1, l2 : ListPtr) : ListPtr;
  52. Var
  53.   tmp : ListPtr;  { resulting list }
  54. begin
  55.   if (l1 = nil) then
  56.     tmp := l2
  57.   else
  58.   if (l2 = nil) then
  59.     tmp := l1
  60.   else
  61.   if l1^.str < l2^.str then
  62.   begin { lesser node first }
  63.     tmp := l1;
  64.     l1 := l1^.next;
  65.   end
  66.   else
  67.   begin
  68.     tmp := l2;
  69.     l2 := l2^.next;
  70.   end;
  71.   MergeAlphaLists := tmp;               { return head of merged sorted list }
  72.   While (l1 <> nil) and (l2 <> nil) do  { traverse lists }
  73.   if l1^.str < l2^.str then
  74.   begin
  75.     tmp^.next := l1; { add the lesser node }
  76.     tmp := l1;       { move ahead }
  77.     l1 := l1^.next;  { next node }
  78.   end
  79.   else
  80.   begin
  81.     tmp^.next := l2; { add the lesser node }
  82.     tmp := l2;       { ahead 1 }
  83.     l2 := l2^.next;  { next node }
  84.   end;
  85.   if (l1 <> nil) then
  86.     tmp^.next := l1   { append remaining nodes }
  87.   else
  88.     tmp^.next := l2;
  89. end; { MergeAlphaLists }
  90.  
  91. { Sorts list l alphabetically }
  92. Function MergeSortAlpha(l : ListPtr) : ListPtr;
  93. Var
  94.   sl1,
  95.   sl2 : ListPtr;
  96. begin
  97.   if l <> nil then                 { empty list? }
  98.     if l^.next <> nil then
  99.     begin   { single node list? }
  100.       inc(progress);
  101.       SplitList(l, sl1, sl2);      { split list into two halves }
  102.       sl1 := MergeSortAlpha(sl1);  { sort the first half }
  103.       sl2 := MergeSortAlpha(sl2);  { sort the second half }
  104.       MergeSortAlpha := MergeAlphaLists(sl1, sl2)  { combine sorted lists }
  105.     end
  106.     else
  107.       MergeSortAlpha := l   { single node is already sorted }
  108.   else
  109.     MergeSortAlpha := nil
  110. end;
  111.  
  112. {
  113. What mergesort does is to split the list into two equal halves.  It then
  114. mergesorts each of these halves, and merges them back together.  The Real work
  115. is done in the merging step.  When the lists are split down to the level of
  116. single node lists they are merged together again in the correct order.  As it
  117. pops out of the recursion the larger lists are sorted so that merging will
  118. still keep them in order because each node is > than the previous one.  This is
  119. probably the most widely used sorting algorithm (don't quote me) because it is
  120. simple but delivers n*log(n) performance like any good algorithm would.
  121. }
  122.